package leetcode.剑指offer.剑指II;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/12/11 16:04
 * @description：https://leetcode-cn.com/problems/Ygoe9J/
 */
public class 剑指_II_81_允许重复选择元素的组合 {
    @Test
    public void test() {
        Solution solution = new Solution();
    }

    class Solution {

        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            List<List<Integer>> ans = new ArrayList<>();
            backtrack(candidates, ans, new ArrayList<>(), target, 0);
            return ans;
        }

        private void backtrack(int[] candidates, List<List<Integer>> ans, ArrayList<Integer> list, int target, int idx) {
            if (target == 0) {
                ans.add(new ArrayList<>(list));
                return;
            }
            if (idx == candidates.length) return;
            backtrack(candidates, ans, list, target, idx + 1);
            if (target - candidates[idx] >= 0) {
                list.add(candidates[idx]);
                backtrack(candidates, ans, list, target - candidates[idx], idx);
                list.remove(list.size() - 1);
            }
        }

        /*private <E> void backtrack(int[] candidates, List<List<Integer>> ans, ArrayList<Integer> list, int target, int idx) {
            if (idx == candidates.length) return;
            if (target == 0) {
                ans.add(new ArrayList<>(list));
                return;
            }
            // 直接跳过
            backtrack(candidates, ans, list, target, idx + 1);

            // 不跳过
            if (target - candidates[idx] >= 0) {
                list.add(candidates[idx]);
                backtrack(candidates, ans, list, target - candidates[idx], idx);
                list.remove(list.size() - 1);
            }
        }*/

    }
}
